#include<stdio.h>
// #define ArrayLen(a)   sizeof(a)/sizeof(a[0])
//12345
int IsBigger(int a,int b)
{
    if(a>b)
        return 1;
    else 
        return 0;
}

//54321
int IsSmaller(int a,int b)
{
    if(a<b)
        return 1;
    else 
        return 0;
}

void Swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

// 1.
void BubbleSort(int *a,int len,int (*Rule)(int,int))
{
    for(int i=0;i<len-1;i++)
    {
        int flag=0;
        for(int j=0;j<len-i-1;j++)
        {
            if(Rule(a[j],a[j+1]))
            {
                int temp;
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flag=1;
            }
        }
        if(flag==0)
        {
            break;
        }
    }
}

// 2.
void InsertSort(int *a,int len)
{
    for(int i=0;i<len;i++)
    {
        int temp=a[i];
        int j=i;
        for(;j>0;j--)
        {
            if(a[j-1]>temp)
            {
                a[j]=a[j-1];
            }
            else
                break;
        }
        a[j]=temp;
    }
}

// 3.
void ChooseSort(int *a,int len)
{
    int left=0;
    int right=len-1;
    while(left<right)
    {
        int min=left;
        int max=right;
        for(int i=left;i<=right;i++)
        {
            if(a[i]<a[min])
                min=i;
            if(a[i]>a[max])
                max=i;
        }
        Swap(&a[left],&a[min]);
        if(max==left)
        {
            max=min;
        }
        Swap(&a[right],&a[max]);

        left++;
        right--;
    }
}

// 4.
// fastSort(a,0,ArrayLen(a)-1);
void fastSort(int *a,int start,int end)
{
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        while(left<right && a[right]>temp)
        {
            right--;
        }

        if(left<right)
        {
            a[left]=a[right];
            left++;
        }

        while(left<right && a[left]<temp)
        {
            left++;
        }

        if(left<right)
        {
            a[right]=a[left];
            right--;
        }

        a[left]=temp;
        fastSort(a,start,left-1);
        fastSort(a,right+1,end);
    }   
}

// int main()
// {
//     int a[]={5,8,6,4,3,7};
//     BubbleSort(a,ArrayLen(a),IsSmaller);
//     for(int i=0;i<ArrayLen(a);i++)
//     {
//         printf("%d ",a[i]);
//     }
//     printf("\n");
// }

// int main()
// {
//     int a[]={5,8,6,4,3,7};
//     InsertSort(a,ArrayLen(a));
//     for(int i=0;i<ArrayLen(a);i++)
//     {
//         printf("%d ",a[i]);
//     }
//     printf("\n");
// }

// int main()
// {
//     int a[]={5,8,6,4,3,7};
//     ChooseSort2(a,ArrayLen(a));
//     for(int i=0;i<ArrayLen(a);i++)
//     {
//         printf("%d ",a[i]);
//     }
//     printf("\n");
// }

// int main()
// {
//     int a[]={5,8,6,4,3,7};
//     fastSort(a,0,ArrayLen(a)-1);
//     for(int i=0;i<ArrayLen(a);i++)
//     {
//         printf("%d ",a[i]);
//     }
//     printf("\n");
// }